package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 组合总和
 * <p>
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * <p>
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * <p>
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * @date 2025/6/13 13:40
 */
public class CombinationSum_39 {

    public static void main(String[] args) {
        CombinationSum_39 combinationSum39 = new CombinationSum_39();

        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        combinationSum39.combinationSum(candidates, target).forEach(System.out::println);
    }

    /**
     * 个解：回溯
     * <p>
     * 分析：
     * <p>
     * 1.树的深度由 path的元素和决定。而组合总和 III的树深度由 k 决定。
     * <p>
     * 2.为什么下一层递归是从 i 开始，而不是 i+1 开始？<br/>
     * ——因为这里元素可以重复使用，递归传入 i，才能保证本层使用元素后，下一层仍然可以使用；如{2,5,3}，第一层使用元素2，下一层仍然可以使用元素2。
     * <p>
     * 3.虽然candidates【元素不重复】，但是，其中的元素【可重复使用】；然而，其余组合问题的元素只能用一次。
     */
    List<List<Integer>> ans = new ArrayList<>();

    List<Integer> path = new ArrayList<>();

    int pathSum = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates.length == 0 || target < 0) return ans;

        backtrack(candidates, target, 0);
        return ans;
    }

    public void backtrack(int[] candidates, int target, int startIndex) {
        // pathSum==target，则记录path
        if (pathSum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // pathSum<target，直接返回，结束本层递归
        if (pathSum > target) return;

        // 横向遍历
        for (int i = startIndex; i < candidates.length; i++) {
            // 记录元素，及元素和
            path.add(candidates[i]);
            pathSum += candidates[i];

            // 向下递归
            // 下层仍从i开始，因为元素可以重复使用
            // 为什么从 i ，而不是 i+1 开始？——因为元素可以重复使用。如{2,2,2}是满足要求的
            backtrack(candidates, target, i);

            // 回溯
            path.remove(path.size() - 1);
            pathSum -= candidates[i];
        }
    }

}
